1. Field of the Invention
The present invention relates to graphics subsystems in computer systems, and more particularly, to the use of texture memory for texture mapping.
2. Description of the Related Art
Modern computer systems are typically configured with graphics subsystems designed to remove some of the graphics burden from the system's central processing unit (CPU). The graphics subsystems act as the interface between the computer and the display device (e.g., a monitor). Since the graphics subsystems contain hardware optimized to perform graphics calculations, graphics application performance may be improved. In addition, since the CPU devotes less clock cycles to performing graphics tasks, non-graphics applications may also see improved performance.
In addition to improving performance, another goal of graphics subsystems is to increase the realism of objects that are displayed by the system. The problem of visual realism, however, is quite complex. Objects in the "real world" include an incredible amount of detail, including subtle variations in color, reflections, and surface irregularities.
A number of different approaches have been used to improve realism and add surface detail to objects that are displayed by computers. A simple approach involves the use of surface-detail polygons to show features (e.g., doors, windows, and lettering) on top of a base polygon (e.g., the side of a building). However, as the surface detail to be represented becomes more intricate, the number of polygons also increases. This in turn reduces performance because graphic subsystems are only capable of manipulating a limited number of polygons before performance is unacceptably degraded.
An alternate approach, known as "texture mapping", maps an image (called a "texture map") onto a surface. A texture map is an image which can be wrapped (mapped) onto a three dimensional (3D) object. An example of a texture map 20 is illustrated in FIG. 1A. Texture map 20 is defined as a collection of texture elements ("texels"), with coordinates U and V (similar to X and Y coordinates on the display or "screen space"). In FIG. 1B, an example of texture mapping is shown. As the figure illustrates, texture map 20 is mapped onto two sides of a three dimensional cube. Another example of texture mapping would be to map an image of a painting with intricate detail onto a series of polygons representing a vase. In many cases, texture mapping achieves more realistic results than the use of surface-detail polygons.
While texture mapping may result in more realistic scenes, awkward side-effects of texture mapping may occur unless the graphics subsystem can apply texture maps with correct perspective. Perspective-corrected texture mapping involves an algorithm that translates pixels from the bitmap texture image (i.e., texels) into display pixels in accordance with the spatial orientation of the surface.
In conjunction with texture mapping, many graphics subsystems utilize bilinear filtering, alpha blending, antialiasing, and mip mapping to further improve the appearance of rendered images. Bilinear filtering improves the appearance of texture mapped surfaces by considering the values of four adjacent texels in order to determine the value of the displayed pixel. Bilinear filtering may avoid the "blockiness" that results from simple point sampling when adjacent display pixel values are defined by a single texel. However, one potential drawback of bilinear filtering is that it requires more memory bandwidth that point sampling.
Alpha blending is a technique that controls the transparency of an object, allowing realistic rendering of translucent surfaces such as glass or water. Additional atmospheric effects that are found in rendering engines include fogging and depth cueing. Both of these techniques obscure an object as it moves away from the viewer. The fog effect is a special case of alpha blending whereby a texture with varying levels of translucency is blended with an object which then seems to disappear into a haze. Depth cueing achieves its effect by lowering the intensity of light on an object so that it appears less prominent as it recedes.
Aliasing refers to the jagged edges that result from displaying a smooth object on a computer display. Aliasing is particularly disconcerting at the edges of texture maps. Antialiasing (i.e., minimizing the appearance of jagged edges) avoids this distraction by reducing the contrast between the edge of an object and the color behind it. This is typically accomplished by adjusting pixel values at or near the edge.
Mip mapping involves storing multiple copies of texture maps, each digitized at a different resolution. When a texture mapped polygon is smaller than the texture image itself, undesirable effects may result. Mip mapping avoids this problem by providing a large version of a texture map for use when the object is close to the viewer, and smaller versions of the texture map for use when the object shrinks from view.
A mip map may be visualized as a pyramid of filtered versions of the same texture map. Each map has one-half the linear resolution of its preceding map, and has therefore one quarter the number of texels. The memory cost of this organization, where the coarsest level has only one texel, is 4/3 (i.e., 1+1/4+1/16+ . . . ) the cost of the original map. The acronym "mip" stands for "multum in parvo", a Latin phrase meaning "many things in a small place". The mip map scheme thus provides pre-filtered textures, one of which is selected at run time for use in rendering. In general, this theoretical level will lie between two adjacent pre-calculated levels, and will therefore require interpolation to the theoretical level. Within each map, bilinear interpolation may be needed if the texel to be looked up is not exactly on the integer boundaries. Similar two-dimensional linear interpolations are computed in each mip map when scaled (u, v) values required for texture table lookup are not integer values. To assure continuity during animation, the effects of the four texels which enclose the scaled (u, v) values are considered, based upon their linear distances from the reference point in texel space. For example, if the scaled (u, v) values are (3.7, 6.8), the weighted average of texels (3, 6), (4, 6), (3, 7), and (4, 7) is taken.
Turning now to FIG. 2, a set of mip maps is shown. As the figure illustrates, each mip map is a two dimensional image, where each successive mip map is one half the size of the previous one. For example, if level 0 (i.e., texture map 20) is sixteen by sixteen texels, then level 1 (mip map 22) will be eight by eight texels, level 2 (mip map 24) will be four by four texels, level 3 (mip map 24) will be two by two texels, and level 4 (mip map 28) will be a single texel. Each subsequent mip map is one half the dimension of the previous mip map. Thus, each subsequent mip map has one quarter the area, number of texels, and resolution of the previous mip map. Note, however, that other ratios are also possible and that mip maps need not be square.
Tri-linear filtering may be used to smooth out edges of mip mapped polygons and prevent moving objects from displaying a distracting `sparkle` resulting from mismatched texture intersections. Trilinear filtering involves blending texels from two neighboring mip maps (e.g., blending texels from mip map 20 and mip map 22). The texel addresses in the neighboring mip maps are related by their addresses. For example, a particular texel at address (U,V) in level N corresponds to the texel at address (U/2, V/2) in level N+1. This is represented by texels 30 and 32 in the figure (each marked with an "x").
To improve texture mapping performance, graphics systems may store mip maps in dedicated memory. The memory may be part of main system memory or may be implemented as dedicated texture memory on a graphics subsystem board. Since this memory must be low latency and have a high bandwidth, dynamic random access memories (DRAMs) do not typically suffice. Instead, more expensive memories with faster access times may employed, e.g., synchronous DRAMs (SDRAMs).
Turning now to FIG. 3, an example of a texture map SDRAM 40 is shown. As illustrated in the figure, SDRAM 40 comprises two independent banks of memory cells, i.e., memory banks 42 and 44 (also referred to herein as "bank A" and "bank B"). Each bank comprises a plurality of rows (e.g., rows 46 and 48). While SDRAMs may vary in size, a typical row may store 512 bytes of data. Note that the term "page" is synonymous with "row" and is used in phrases like "page-miss" (an attempt to read from a row which not currently active). Each bank may only have one row active at a particular time (see rows 46 and 48), and a bank must be deactivated for a predetermined time period before a different row may be activated.
The cost of SDRAMs necessarily limit the amount of memory that may be included in a graphics subsystem. In addition to size limitations, other factors may further complicate the process of storing mip maps into memory. For example, during trilinear filtering, it is often desirable to access neighboring mip maps (e.g., level 0 and level 1) at the same time (or one immediately after the other).
Turning now to FIG. 4, the difficulties in implementing this feature are illustrated. In the example storage method shown in the figure, memory banks 42 and 44 are treated as a single linear array. Each mip map is stored in scan line order (i.e., with the U coordinate varying most rapidly, then the V coordinate, then the mip map level). While simple to implement, this method has drawbacks. As previously noted, during trilinear filtering a particular texel may be read from a level and then blended with a corresponding texel from a neighboring level. This may cause page faults if the configuration from FIG. 4 is used. For example, a first texel 50 at address (U,V) within level 0 in memory bank 42 may be read during a first clock cycle. This read actives row 60 in memory bank 42. During the next clock cycle, the graphics subsystem attempts to read the corresponding texel 52 at address (U/2, V/2) in level two. However, since the desired texel 52 is in a different row 62 within memory bank 42, a page miss occurs and memory bank 42 must be deactivated for a predetermined time period before row 62 may be activated.
For these reasons, a method for efficiently storing texture maps is desired. In particular, a method allowing rapid access to corresponding texels in neighboring mip map levels is needed.